package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import org.junit.Test;

/**
 * @author By ZengPeng
 */
public class 力扣_114_二叉树展开为链表 {
    @Test
    public void main() {
        TreeNode treeNode = TreeNode.initRoot();
        flatten(treeNode);
        System.out.println(treeNode);
    }

    /**
    题目：给你二叉树的根结点 root ，请你将它展开为一个单链表：
         展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
         展开后的单链表应该与二叉树 先序遍历 顺序相同。

     示例 1：
     输入：root = [1,2,5,3,4,null,6]
     输出：[1,null,2,null,3,null,4,null,5,null,6]

     示例 2：
     输入：root = []
     输出：[]

     示例 3：
     输入：root = [0]
     输出：[0]

    分析：【P 💔💔💔💔】
       1.深度优先：先将左子树转换为链表，得到的最后一个节点，节点指向右子树递归后的结果  -- 需要得到两个结果：顶级节点、末节点  不是很好操作
                --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
                --时长：25分钟

    边界值 & 注意点：
       1.
     **/
    public void flatten(TreeNode root) {
       if(root==null)return;
       dfs(root);
    }

    //递归三步曲：单步操作、终止条件、返回值
    private TreeNode dfs(TreeNode root) {
        if(root.left==null && root.right==null) return root;
        TreeNode right = root.right;
        TreeNode left = root.left;
        if(root.left!=null){//左节点不为空，放到右边，然后再链化 原先的左链表
            root.right = root.left;
            root.left = null;
            root =  dfs(left);//得到链化后的 左子树尾节点，用于关联右子树
        }
        if(right != null) {
            root.right= right;//关联右子树
            return dfs(right);//链化右子树，返回最下节点
        }
        return root;
    }
}
